// Copyright 2008 Silvio Massari
//
// This file is part of SilvioMassari.Automata
//
// SilvioMassari.Automata is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// SilvioMassari.Automata is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with SilvioMassari.Automata.  If not, see <http://www.gnu.org/licenses/>.
				
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace SilvioMassari.Automata
{
    public class Nda<S, T>
    {
        protected State<S, T> _initialState = null;
        protected T _value;
        protected Dictionary<Pattern<S>, Transition<S, T>> _patterns = new Dictionary<Pattern<S>, Transition<S, T>>();

        public Nda()
        {
            Clear();
        }

        public void Clear()
        {
            _initialState = new State<S, T>();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            foreach (KeyValuePair<Pattern<S>, Transition<S, T>> pair in _patterns)
            {
                sb.Append(pair.Key.ToString());
                sb.Append(": ");
                sb.Append(pair.Value.ToString());
                sb.Append(" = ");
                sb.AppendLine(pair.Value.To.Value.ToString());
            }
            return sb.ToString();
        }

        public virtual string ToString(bool states)
        {
            if (!states)
            {
                return ToString();
            }

            StringBuilder sb = new StringBuilder();
            List<State<S, T>> list = new List<State<S, T>>();

            int index = 0;
            list.Add(_initialState);

            while (index < list.Count)
            {
                bool printed = false;
                State<S, T> state = list[index];
                foreach (State<S, T> aux in state.NextByNull)
                {
                    printed = true;
                    if (!list.Contains(aux))
                    {
                        list.Add(aux);
                    }
                    int auxIndex = list.IndexOf(aux);
                    sb.AppendFormat("{0}{2} ---> {1}", index, auxIndex, state.Finalization ?  "F": string.Empty);
                    sb.Append(Environment.NewLine);
                }

                foreach (KeyValuePair<S, State<S, T>> pair in state.NextByChar)
                {
                    printed = true;
                    State<S, T> aux = pair.Value;
                    if (!list.Contains(aux))
                    {
                        list.Add(aux);
                    }
                    int auxIndex = list.IndexOf(aux);
                    sb.AppendFormat("{0}{3} -{1}-> {2}", index, pair.Key, auxIndex, state.Finalization ? "F" : string.Empty);
                    sb.Append(Environment.NewLine);
                }
                if (!printed)
                {
                    sb.AppendFormat("{0}{1}", index, state.Finalization ? "F" : string.Empty);
                    sb.Append(Environment.NewLine);
                }

                index++;
            }
            return sb.ToString();
        }

		public void AddPattern(string pattern, T value)
		{
			AddPattern(new PatternString<S>(pattern), value);
		}

        public void AddPattern(Pattern<S> pattern, T value)
        {
            Stack<Transition<S, T>> stack = new Stack<Transition<S, T>>();
            List<Transition<S, T>> list = new List<Transition<S, T>>();

            if (pattern == null || pattern.Length == 0)
            {
                throw new ArgumentNullException("pattern");
            }

            int count = pattern.Length;
            bool implicitAnd = false;
            for (int index = 0; index < count; index++)
            {
				Element<S> current = (Element<S>)pattern[index];

				if (current is ElementData<S>)
				{
					if (implicitAnd)
					{
						TransitionAnd<S, T> transition = new TransitionAnd<S, T>();
						ProcessOperator(stack, list, transition);
					}
					list.Add(new TransitionElement<S, T>((ElementData<S>)current));
					implicitAnd = true;
				}
				else if (current is ElementOperatorAnd<S>)
				{
					implicitAnd = false;
					TransitionAnd<S, T> transition = new TransitionAnd<S, T>();
					ProcessOperator(stack, list, transition);
				}
				else if (current is ElementOperatorOr<S>)
				{
					implicitAnd = false;
					TransitionOr<S, T> transition = new TransitionOr<S, T>();
					ProcessOperator(stack, list, transition);
				}
				else if (current is ElementOperatorMany<S>)
                {
                    implicitAnd = true;
                    TransitionMany<S, T> transition = new TransitionMany<S, T>();
                    ProcessOperator(stack, list, transition);
                }
                else if (current is ElementOperatorOpen<S>)
                {
					if (implicitAnd)
					{
						TransitionAnd<S, T> transition = new TransitionAnd<S, T>();
						ProcessOperator(stack, list, transition);
					}
					implicitAnd = false;
					stack.Push(new TransitionAsoc<S, T>());
                }
                else if (current is ElementOperatorClose<S>)
                {
                    implicitAnd = true;
                    Transition<S, T> transition = null;
                    while (stack.Count > 0)
                    {
                        transition = stack.Pop();
                        if (transition is TransitionAsoc<S, T>)
                        {
                            break;
                        }
                        list.Add(transition);
                        transition = null;
                    }
                    if (transition == null)
                    {
                        throw new ApplicationException("Syntax error. Falta un par�ntesis izquierdo.");
                    }
                }
                else
                {
					throw new ApplicationException("syntax error.");
                }
            } // end for

            while (stack.Count > 0)
            {
                list.Add(stack.Pop());
            }

            foreach (Transition<S, T> transition in list)
            {
                Transition<S, T>[] operandos = null;
                if (transition is TransitionAnd<S, T> ||
                    transition is TransitionOr<S, T>)
                {
                    operandos = new Transition<S, T>[2];
                    operandos[0] = stack.Pop();
                    operandos[1] = stack.Pop();
                    transition.Init(operandos);
                    stack.Push(transition);
                }
                else if (transition is TransitionMany<S, T>)
                {
                    operandos = new Transition<S, T>[1];
                    operandos[0] = stack.Pop();
                    transition.Init(operandos);
                    stack.Push(transition);
                }
                else
                {
                    stack.Push(transition);
                }
            } // end foreach

            System.Diagnostics.Debug.Assert(stack.Count == 1);

            Transition<S, T> finalTransition = stack.Pop();
            finalTransition.To.Finalization = true;
            finalTransition.To.Value = value;
            _initialState.NextByNull.Add(finalTransition.From);
            _patterns.Add(pattern, finalTransition);
        }

        private void ProcessOperator(Stack<Transition<S, T>> stack, List<Transition<S, T>> list, TransitionOperator<S, T> newTransitionOperator)
        {
            while (stack.Count > 0)
            {
                TransitionOperator<S, T> topTransitionOperator = stack.Peek() as TransitionOperator<S, T>;
                if (topTransitionOperator.Precedence >= newTransitionOperator.Precedence)
                {
                    list.Add(stack.Pop());
                }
                else
                {
                    break;
                }
            }
            stack.Push(newTransitionOperator);
        }

		public bool Process(string token)
		{
			if (typeof(S) != typeof(char))
			{
				throw new ApplicationException("Invalid operation. S type must be a char!");
			}

			List<ElementData<S>> elements = new List<ElementData<S>>();

			if (token != null)
			{
				foreach (char c in token)
				{
					elements.Add(new ElementData<S>((S)Convert.ChangeType(c, typeof(S))));
				}
			}

			return Process(elements.ToArray());
		}

		public bool Process(ElementData<S>[] token)
        {
            List<State<S, T>> s = new List<State<S, T>>();
            _initialState.MoveNull(s);

			int count = token == null ? 0 : token.Length;

            for (int i = 0; i < count; i++)
            {
                S element = token[i].Value;
                List<State<S, T>> s2 = new List<State<S, T>>();
                foreach (State<S, T> state in s)
                {
                    state.Move(s2, element);
                }
                s = s2;
            }

			foreach (State<S, T> state in s)
            {
                if (state.Finalization)
                {
                    _value = state.Value;
                    return true;
                }
            }
            return false;
        }

        public T Value
        {
            get { return _value; }
        }

        protected void MoveNull(List<State<S, T>> fromStates)
        {
            foreach (State<S, T> state in fromStates)
            {
                state.MoveNull(fromStates);
            }
        }

        protected void Move(List<State<S, T>> fromStates, S element)
        {
            foreach (State<S, T> state in fromStates)
            {
                state.Move(fromStates, element);
            }
        }
    }
}
